#include <vector>
#include <iostream>
using namespace std;

void siftDown(vector<int>& vecArr,int cur,int n){
	
	while(cur<=n){
		int nLarge=cur;
		int left=cur*2+1;
		int right=cur*2+2;
		if(left<=n && vecArr[nLarge]<vecArr[left]){
			nLarge=left;
		}
		if(right<=n && vecArr[nLarge]<vecArr[right]){
			nLarge=right;
		}
		
		if(nLarge==cur){
			break;
		}
		swap(vecArr[nLarge],vecArr[cur]);
		cur=nLarge;
	}
}
void heapSort(vector<int>& vecArr){
	
	int n=vecArr.size();
	for(int i=n/2-1;i>=0;--i){
		siftDown(vecArr,i,n-1);
	}
	
	for(int i=n-1;i>=0;--i){
		swap(vecArr[i],vecArr[0]);
		siftDown(vecArr,0,i-1);
	}
	
}

void Print(const vector<int>& vecArr){
	
	for(int i=0;i<vecArr.size();++i){
		cout<<vecArr[i]<<' ';
	}
	cout<<endl;
}
int main(){
	
	vector<int> vecArr({5,1,5,2,10,9,8});
	Print(vecArr);
	heapSort(vecArr);
	Print(vecArr);
	return 0;
}
